今天，我請 chatgpt 幫我重寫我的 leetcode 743 的程式碼，發現一個 C++ 類似於 js 的解構賦值（destructuring assignment）的寫法耶! 而這寫法是開始於 C11++，覺得這寫法讓程式碼小小變乾淨。

C++17 及之後的寫法（結構化綁定）：

// `graph[tp_n]` 是 `vector<pair<int, int>>`
for (auto [neighbor, weight] : graph[tp_n]) {
    // 使用 neighbor 和 weight
    // ...
}

C++17 之前的寫法：

for (const auto& p : graph[tp_n]) {
    int neighbor = p.first;
    int weight = p.second;
    // 使用 neighbor 和 weight
}

743. Network Delay Time (medium)

題目解釋:
給定一個由 n 個節點組成的網絡，標記為 1 到 n。另外再給一個二維陣列，其意義為 times[i] = (ui, vi, wi)給一個 ui 節點到 vi 節點 需要的時 wi 時間。
給定節點 k ，從結點 k 發送訊號。返回所有 n 個節點接收到訊號所需的最短時間。如果不可能所有節點都收到訊號，則回傳 -1。

想法:
"返回所有節點接受訊息的最短時間"， 也就是返回最晚收到訊息節點的時間，這樣就所有節點都收到了。 然而要求要"最短時間"，因此我們就得到 k 到每個節點最短時間 (路徑)。

要找到從 k 到所有節點的最短路徑，這可以用 Dijkstra 演算法 來解決，因為它專門解決單源最短路徑問題。

Dijkastra

核心是個 Greedy 算法

定義 dist[i] 表示從起點節點 k 到節點 i 的最短距離。

1. 每次都挑離 src 最近的節點(v)，並確定 v 與 src 的距離。 (此節點與 src 的最短路在未來將不再改變)
2. 之後對 v 的未被確認的相鄰節點的邊做鬆弛操作 (relaxation)

挑選最近的節點這部分，使用 min heap (priority queue)輔助，此資料結構內是存尚未確定節點的最短距離。

C++ 的 priority queue (pq) 用法如下

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

這 pq 裡存儲的值類型是 pair<int, int>，表示 {距離, 節點}。我們需要由小到大的做排序，因此使用 greater<pair<int, int>> 作為比較器，這樣可以實現「由小到大」的排序方式，保證每次都能取出當前距離最小的節點。 (使用 vector<pair<int, int>> 作為底層存儲結構)

另外還需要 isVisited 陣列紀錄此節點是否已決定是最短路徑的，因為在 Dijkstra 演算法中 pq 裡可能會存在多個不同的路徑到同一個節點，而這些路徑的距離可能不同。當我們取出一個節點時，只有第一次取出的最短路徑是正確的(因 min heap)，後面出現的同一節點的距離則會是過時或次優的，所以可以跳過。因此假設不使用 isVisited 來記錄是否已處理過的節點 ? 會導致重複計算節點的距離，從而降低效率。

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        // 建立鄰接表，graph[i] 存儲從節點 i 到其他節點的邊及其權重
        vector<vector<pair<int, int>>> graph(n);
        for (auto& edge : times) {
            int u = edge[0] - 1, v = edge[1] - 1, w = edge[2];
            graph[u].push_back({v, w});
        }

        // dist[i] 表示從起點 k 到節點 i 的最短距離，初始值為無限大
        vector<int> dist(n, INT_MAX);
        dist[k - 1] = 0; // 起點到自己的距離為 0

        // isVisited[i] 表示節點 i 是否已經被處理過
        vector<bool> isVisited(n, false);

        // 優先隊列（最小堆），根據最短距離進行排序，存儲 pair<距離, 節點>
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        pq.push({0, k - 1}); // 起點距離為 0

        while (!pq.empty()) {
            // 取出當前距離最小的節點
            auto [currentDist, u] = pq.top();
            pq.pop();

            // 如果該節點已經處理過，跳過
            if (isVisited[u]) continue;
            isVisited[u] = true;

            // 對該節點的鄰接邊進行鬆弛操作
            for (auto& [v, w] : graph[u]) {
                if (!isVisited[v] && currentDist + w < dist[v]) {
                    dist[v] = currentDist + w;
                    pq.push({dist[v], v});
                }
            }
        }

        // 找出最遠的距離
        int maxDist = *max_element(dist.begin(), dist.end());
        return maxDist == INT_MAX ? -1 : maxDist;
    }
};